#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

from random import randint


class Solution:
    def kthLargestElement(self, k, A=None):
        self.array = A or self.array
        len_arr = len(self.array)
        assert 0 < k <= len_arr

        # self.k = k - 1         # self.k 指的时索引, 下标从0开始
        self.k = (len_arr + 1 - k) - 1 # 我们的内部算法找的是第k, 即第k小的数.从0开始

        # [start, end)
        start, end = 0, len_arr
        return self.quick_get_kth(start, end)

    def quick_get_kth(self, start, end):
        ''' [start, end)
            快排式查找kth element
        '''
        assert start <= (self.k) < end
        if end - start == 1:
            assert self.k == start
            return self.array[start]

        self.shuffle_point(start, end)          # NOTE: 防止在排序数据上获得较差性能
        cmp_idx = start
        # print('start, end, self.k, cmp_idx (%s, %s, %s, %s)' % (start, end, self.k, cmp_idx))

        # range不包括end
        move_idx = start + 1
        for index in range(start+1, end):
            # 从start or start+1, 因为start是cmp_idx
            if self.array[index] < self.array[cmp_idx]:
                self.swap(index, move_idx)
                move_idx += 1
        self.swap(cmp_idx, move_idx-1)
        cmp_idx = move_idx-1

        # print(self.array)
        # print(cmp_idx)

        if cmp_idx == self.k:
            return self.array[cmp_idx]
        if cmp_idx < self.k:
            return self.quick_get_kth(cmp_idx + 1, end)
        if cmp_idx > self.k:
            return self.quick_get_kth(start, cmp_idx)        # 因为是开区间end), 所以cmp_idx不减1

    def shuffle_point(self, start, end):
        # [start, end)
        # 因为randint是闭区间, 所以需要end-1
        # 这里也可以选取中间数
        # choice_point = randint(start, end-1)
        choice_point = start + (end - start) // 2
        self.swap(start, choice_point)

    def swap(self, i1, i2):
        if i1 == i2: return
        l = self.array
        l[i1], l[i2] = l[i2], l[i1]



def main():
    print("start main")
    from numpy.random import permutation as per

    for i in range(100):
        s = Solution()
        l = list(per(10))
        print(l)
        r = s.kthLargestElement(2, l)
        assert r == 8, r

    l = [7, 2, 8, 4, 3, 0, 9, 5, 1, 6]
    print(l)
    s = Solution()
    r = s.kthLargestElement(2, l)
    print(r)

    # print(s.kthLargestElement(1, [2, 3,5, 7,1 ,6, 9]))
    # print(s.kthLargestElement(1, [10, 12, 11,1,3,2,5,4,6,7,8,9]))
    # # print(s.kthLargestElement(1))
    # print(s.kthLargestElement(2))
    # print(s.array)
    # print(s.kthLargestElement(3))
    # print(s.kthLargestElement(5))
    # print(s.kthLargestElement(6))
    # print(n)
    # print(s.kthLargestElement(10, [1,2,3,4,5,6,8,9,10,7]))


if __name__ == "__main__":
    main()
